1. Field of the Invention
This invention relates to the logic synthesis technology to generate the LUT circuits used in look-up table (LUT) cascade networks or LUT-type FPGAs, to implement a multiple-output logic function.
2. Description of the Related Art
Recently, LUT-type Field Programmable Gate Arrays (FPGAs) are widely used in designs of various electronic networks. (For example, see non-patent literature 1˜3). An LUT-type FPGA consists of a large number of configurable logic blocks (CLBs) arranged in a two-dimensional array, and plural vertical and horizontal routing lines located between CLBs. In each cross-point of the routing lines, there is a programmable switch block (SB) so that the reprogramming of the interconnection between them are possible. Also each CLB and routing lines are connected by a reconfigurable connection block (CB). And, at the end of each routing line, there is an input/output part (I/O part) sends and receives signal to and from the outside of the FPGA. Each CLB has one or more multi-input single-output LUTs and multiplexers (MUXs) to perform the logic operation. In an LUT-type FPGA, by reconfiguring SBs, CBs and CLBs, we can realize various combinational logic circuits by interconnecting LUTs that store desired multi-input single-output logic functions, according to the object.
On the other hand, to realize faster circuit than FPGAs, LUT cascade logic circuits have been proposed (for example, see non-patent literature 4,5). An LUT cascade logic circuit has a structure consisting of multi-input multi-output LUTs connected in a cascade. To each LUT, in addition to the external inputs, the outputs from the LUT of the preceding stage, are connected as inputs. And, from the LUT of the final stage, one or more output variables are produced. The objective logic function are decomposed into plural multiple-output logic functions, and each multiple-output logic function are stored in each LUT. In this way, we can implement the desired operations of multiple-output logic function by using an LUT cascade logic circuit.
In order to apply the above-mentioned LUT-type FPGA or LUT cascade logic circuit in the practical logic circuit design, first, we represent the desired objective logic function as a compound logic function by decomposing the objective function. Where the compound logic function is obtained by composing the decomposition function, i.e., the plural logic functions produced by functional decompositions. That is, let the objective logic function be denoted by ƒ(X), where {X} denotes the set of the input variables. When the objective logic function is decomposed in the form ƒ(X1,X2)=g(h(X1),X2) ({X1}⊂{X}, {X2}⊂{X}, {X1}∩{X2}=φ, {X1}∪{X2}={X}), g(h(X1),X2) is the compound function of g and h.
In this description of the patent, the symbols X and Y denote the ordered set of the input variables, and output variables, respectively, while the symbols {X}, {Y} denotes the unordered set of the input and output variables, respectively.
From the above-mentioned functional decomposition, we have two decomposition function h(X1) and g(h,X2). Such functional decomposition is not always possible, but many practical functions, such as control circuits and arithmetic circuits used in computer are decomposable (see non-patent literature 6). Also, when the decomposition function g(h,X2) is also decomposable, we can iterate a similar functional decompositions.
And, realize each decomposition function by a separate LUT, and connect these LUTs in a network structure or in a cascade structure to form compound logic function. In this way, we can realize the objective logic function by using LUT-type FPGAs or LUT cascade logic circuits.
When the objective function has a single output, by using above-mentioned functional decomposition method, we can relatively easily implement the function by the logic circuit consisting of LUTs (for example, see non-patent literature 4, 5 reference).
On the other hand, when the objective logic function has multiple outputs, as for the synthesis technique to implement the objective logic function as an LUT circuit, the following methods are known.
(1) A method to used a multi terminal binary decision diagram (MTBDD) (See non-patent literature 7, 8).
(2) A method to realize by partitioning the outputs into several groups (See non-patent literature 7).
(3) A method to used a partition theory (See non-patent literature 9, 10).
(4) A method using substitution (See non-patent literature 11).
(5) A method to use hyper function (non-patent literature 12 reference)
(6) A method to use time-division multiplexing represented by the Encoded Characteristic Function for Non-zeros (ECFN) (See non-patent literature 4, 5).
(7) Combinations of some of above methods (See non-patent literature 11).